/*
 * @Author: liusheng
 * @Date: 2022-04-23 21:21:58
 * @LastEditors: liusheng
 * @LastEditTime: 2022-04-23 21:49:35
 * @Description: 剑指 Offer II 040. 矩阵中最大的矩形
 * email:liusheng613@126.com
 * Copyright (c) 2022 by liusheng/liusheng, All Rights Reserved. 
 * 
 剑指 Offer II 040. 矩阵中最大的矩形
给定一个由 0 和 1 组成的矩阵 matrix ，找出只包含 1 的最大矩形，并返回其面积。

注意：此题 matrix 输入格式为一维 01 字符串数组。

 

示例 1：



输入：matrix = ["10100","10111","11111","10010"]
输出：6
解释：最大矩形如上图所示。
示例 2：

输入：matrix = []
输出：0
示例 3：

输入：matrix = ["0"]
输出：0
示例 4：

输入：matrix = ["1"]
输出：1
示例 5：

输入：matrix = ["00"]
输出：0
 

提示：

rows == matrix.length
cols == matrix[0].length
0 <= row, cols <= 200
matrix[i][j] 为 '0' 或 '1'
 */

#include "header.h"
/*
using Largest Rectangle of histogram

similar question:221 https://leetcode.com/problems/maximal-square/
*/
class Solution {
public:
    int maximalRectangle(vector<string>& matrix) {
        int rows = matrix.size();
        if (!rows)
        {
            return 0;
        }
        int cols = matrix[0].size();
        if (!cols)
        {
            return 0;
        }

        int maxArea = 0;

        //for every row convert to rectangle height and width
        //then use monototic ascend to solve it(same as max rectangle area solution) 
        vector<vector<int>> heights(rows,vector<int>(cols,0)); 
        
        for (int i = 0; i < rows; ++i)
        {
            stack<int> ascendRowStack;
            for (int j = 0; j < cols; ++j)
            {
                if (matrix[i][j] == '1')
                {
                    heights[i][j] = i == 0 ? matrix[i][j] - '0': heights[i-1][j] +  matrix[i][j] - '0';
                }
                else
                {
                    heights[i][j] = 0;
                }
                
                while (!ascendRowStack.empty() && heights[i][j] < heights[i][ascendRowStack.top()])
                {
                    int prevCol = ascendRowStack.top();
                    int height = heights[i][prevCol];
                    ascendRowStack.pop();
                    int width = ascendRowStack.empty() ? j : j - ascendRowStack.top() - 1;
                    // printf("000 width:%d,height:%d\n",width,height);
                    maxArea = max(maxArea,width * height);                   
                }

                ascendRowStack.push(j);
            }

            while (!ascendRowStack.empty())
            {
                int height = heights[i][ascendRowStack.top()];
                ascendRowStack.pop();
                int width = ascendRowStack.empty() ? cols : cols - ascendRowStack.top() - 1;
                // printf("111 width:%d,height:%d\n",width,height);
                maxArea = max(maxArea,width * height);
            }

        }

        return maxArea;
    }
};

/*
same as solution1
*/
class Solution2 {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {   
        int rows = matrix.size();
        if(!rows)
        {
            return 0;
        }
        int cols = matrix[0].size();
        if (!cols)
        {
            return 0;
        }
        
        vector<vector<int>> rectHeight(rows,vector<int>(cols,0));//hold every row to the up and left's rectangle height
        int maxArea = 0;
        for (int i = 0; i < rows; ++i)
        {
            stack<int> monotonicIncrSt;
            for (int j = 0; j < cols; ++j)
            {
                if (matrix[i][j] == '0')
                {
                    rectHeight[i][j] = 0;
                }
                else
                {
                    rectHeight[i][j] = i == 0 ? matrix[i][j] - '0': rectHeight[i-1][j] + matrix[i][j] - '0';
                }
                
                while (!monotonicIncrSt.empty() && rectHeight[i][j] < rectHeight[i][monotonicIncrSt.top()])
                {
                    int height = rectHeight[i][monotonicIncrSt.top()];
                    monotonicIncrSt.pop();
                    int width = monotonicIncrSt.empty() ? j : j - monotonicIncrSt.top() - 1;
                    maxArea = max(maxArea,width * height);
                }
                monotonicIncrSt.push(j);
            }
            
            while (!monotonicIncrSt.empty())
            {
                int height = rectHeight[i][monotonicIncrSt.top()];
                monotonicIncrSt.pop();
                int width = monotonicIncrSt.empty() ? cols : cols - monotonicIncrSt.top() - 1;
                maxArea = max(maxArea,width * height);
            }
        }
        
        return maxArea;
    }
};
